/*
    建图、链式前向星、拓扑排序

    前置知识 : 讲解013-数组实现队列、讲解019-算法笔试更推荐静态空间的方式、讲解025-堆结构

    有向 vs 无向、不带权 vs 带权。入参一般为 节点数量n和所有的边 或者 直接给图
    建图的三种方式，我们图解一下！
    1，邻接矩阵（适合点的数量不多的图）
    2，邻接表（最常用的方式）
    3，链式前向星（空间要求严苛情况下使用。比赛必用，大厂笔试、面试不常用）

    【必备】课程里涉及图的内容：
    建图、链式前向星、拓扑排序、最小生成树、bfs、双向广搜
    最短路（Dijkstra、A*、Floyd、Bellman-Ford、SPFA）

    【挺难】课程里涉及图的内容：
    基环树、欧拉回路、割点和桥、强连通分量、双连通分量、最大流、费用流、二分图的最大匹配

    ================================================

    题目1
    三种方式的建图和遍历

    ================================================

    拓扑排序
    每个节点的前置节点都在这个节点之前

    要求：有向图、没有环

    拓扑排序的顺序可能不只一种。拓扑排序也可以用来判断有没有环。
    1）在图中找到所有入度为0的点
    2）把所有入度为0的点在图中删掉，重点是删掉影响！继续找到入度为0的点并删掉影响
    3）直到所有点都被删掉，依次删除的顺序就是正确的拓扑排序结果
    4）如果无法把所有的点都删掉，说明有向图里有环

    注意：本节课讲解拓扑排序直接使用解决的题目，下节课会讲拓扑排序扩展技巧解决的题目

    ================================================

    题目2
    拓扑排序模版
    邻接表建图（动态方式）
    链式前向星建图（静态方式）
    测试链接 : https://leetcode.cn/problems/course-schedule-ii
    测试链接 : https://www.nowcoder.com/practice/88f7e156ca7d43a1a535f619cd3f495c

    ================================================

    题目3
    字典序最小的拓扑排序
    要求返回所有正确的拓扑排序中 字典序最小 的结果
    建图请使用链式前向星方式，因为比赛平台用其他建图方式会卡空间
    测试链接 : https://www.luogu.com.cn/problem/U107394

    注意：解决该问题需要使用小根堆，不熟悉的同学去看，讲解025-堆结构

    ================================================

    题目4
    火星词典
    现有一种使用英语字母的火星语言
    这门语言的字母顺序对你来说是未知的。
    给你一个来自这种外星语言字典的字符串列表 words
    words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
    如果这种说法是错误的，并且给出的 words 不能对应任何字母的顺序，则返回 ""
    否则，返回一个按新语言规则的 字典递增顺序 排序的独特字符串
    如果有多个解决方案，则返回其中任意一个
    words中的单词一定都是小写英文字母组成的
    测试链接 : https://leetcode.cn/problems/alien-dictionary

    ================================================

    题目5
    戳印序列
    你想最终得到"abcbc"，认为初始序列为"?????"。印章是"abc"
    那么可以先用印章盖出"??abc"的状态，
    然后用印章最左字符和序列的0位置对齐，就盖出了"abcbc"
    这个过程中，"??abc"中的a字符，被印章中的c字符覆盖了
    每次盖章的时候，印章必须完全盖在序列内
    给定一个字符串target是最终的目标，长度为n，认为初始序列为n个'?'
    给定一个印章字符串stamp，目标是最终盖出target，但是印章的使用次数必须在10*n次以内
    返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成
    上面的例子返回[2,0]，表示印章最左字符依次和序列2位置、序列0位置对齐盖下去，就得到了target
    如果不能在10*n次内印出序列，就返回一个空数组
    测试链接 : https://leetcode.cn/problems/stamping-the-sequence

*/